function maxSort(arr) {
  let result = [...arr];
  for (let i = 0, len = result.length; i < len; i++) {
    let minV = Math.min(...result.slice(i));
    let pos = result.indexOf(minV, i);
    result.splice(pos, 1);
    result.unshift(minV);
  }
  return result.reverse();
}

let testArr = [1, 24, 235, 46, 533, 62, 71, 8, 9, 10, 3932, 23, 42, 495, 392];
// console.log(maxSort(testArr));

function getFnRunTime(fn) {
  let len = testArr.length;
  let startTime = Date.now(),
    endTime;
  let result = fn(testArr);
  endTime = Date.now();
  console.log(result);
  console.log(
    `total time:${endTime - startTime}ms`,
    "test array'length:" + len,
    result.length
  );
}
console.log(getFnRunTime(maxSort));

function swap(arr, indexA, indexB) {
  [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
}
function bubbleSort1(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }

  return arr;
}
console.log("bubbleSort1", bubbleSort1(testArr));

function bubbleSort2(arr) {
  let i = arr.length - 1;

  while (i > 0) {
    let pos = 0;

    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j;
        swap(arr, j, j + 1);
      }
    }
    i = pos;
  }

  return arr;
}
console.log("bubbleSort2", bubbleSort2(testArr));

function bubbleSortx(testArr) {
  for (let rest = testArr.length - 1; rest >= 0; rest--) {
    for (let i = 0; i < rest; i++) {
      if (testArr[i] > testArr[i + 1]) {
        let tem = testArr[i];
        testArr[i] = testArr[i + 1];
        testArr[i + 1] = tem;
      }
    }
  }
  return testArr;
}
console.log(bubbleSortx(testArr), "bubbleSortx");

function selectionSort(testArr) {
  for (let j = 0; j < testArr.length - 1; j++) {
    // 定义一个临时变量存放最小值索引
    let minIndex = j;
    for (let i = j + 1; i < testArr.length; i++) {
      if (testArr[minIndex] > testArr[i]) {
        minIndex = i;
      }
    }
    let temp = testArr[j];
    testArr[j] = testArr[minIndex];
    testArr[minIndex] = temp;
  }

  return testArr;
}
console.log(selectionSort(testArr), "selectionSort");
/**
 * 希尔排序
 * 核心：通过动态定义的 gap 来排序，先排序距离较远的元素，再逐渐递进
 * @param {*} arr
 * 耗时：15ms
 */
function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);

  while (gap > 0) {
    // gap距离
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let preIndex = i - gap;

      while (arr[preIndex] > temp) {
        arr[preIndex + gap] = arr[preIndex];
        preIndex -= gap;
      }
      arr[preIndex + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }

  return arr;
}
console.log("shellSort", shellSort(testArr));

/**
 * 归并排序
 * @param {*} arr
 * 耗时 30ms
 */
function concatSort(arr) {
  const len = arr.length;

  if (len < 2) {
    return arr;
  }

  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return concat(concatSort(left), concatSort(right));
}

function concat(left, right) {
  const result = [];

  while (left.length > 0 && right.length > 0) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }

  return result.concat(left, right);
}
console.log("concatSort", concatSort(testArr));
